import math
import random


class Player(object):
    filler = "filler"

    def __init__(self):
        super(Player, self).__init__()
        self.first_round_number = None
        self.total_moves = 0
        self.my_hunts = 0
        self.current_reputation = 0.0
        self.tracker = Tracker()
        self.round_up = True
        self.is_first_round = True
        self.target_modifier = 1.0
        self.chance_modifier = 1.0

    #### HungerGames API ####

    # even though I've tested quite thoroughly, I like to err on the side of caution
    def hunt_choices(self, round_number, current_food, current_reputation, m, player_reputations):
        try:
            return self._hunt_choices(round_number, current_food, current_reputation, m, player_reputations)
        except Exception:
            return ["s"] * len(player_reputations)

    # even though I've tested quite thoroughly, I like to err on the side of caution
    def hunt_outcomes(self, food_earnings):
        try:
            self._hunt_outcomes(food_earnings)
        except Exception:
            pass

    def round_end(self, award, m, number_hunters):
        # this method has no contribution to the strategy
        pass

    #### end ####

    def _distribution_index(self, reputation, granularity=8):
        if reputation == 1.0:
            return granularity - 1

        step = 1.0 / granularity
        factor = 0

        while reputation >= factor * step:
            factor += 1

            if reputation < factor * step:
                return factor - 1

        return factor

    def _distribution_value(self, index, granularity=8):
        step = (1.0 / granularity)
        return (index * step) + (step / 2.0)

    def _target_hunts(self, goal_rep, num_players):
        delta = goal_rep - self.current_reputation
        target_rep = self.current_reputation + delta
        new_rep_max = float(self.my_hunts + num_players) / self.next_total_moves
        new_rep_min = float(self.my_hunts) / self.next_total_moves

        if target_rep >= new_rep_max:
            return num_players
        elif target_rep <= new_rep_min:
            return 0

        real_target_hunts = target_rep * num_players
        int_target_hunts = int(target_rep * num_players)

        if real_target_hunts != int_target_hunts:
            # if the target hunts aren't an integer
            if self.round_up and int_target_hunts < num_players:
                self.round_up = False
                return int_target_hunts + 1
            elif not self.round_up:
                # int_target_hunts has already been rounded down
                # by the int conversion
                self.round_up = True

        return int_target_hunts

    def _determine_target_hunts(self, player_reputations):
        # for the first round, we go 50/50.
        # this is the best option to be able to achieve
        # a reputation of the masses.
        goal_rep = .5
        num_players = len(player_reputations)

        # go for a reputation of the masses to mask from detection
        if not self.is_first_round:
            average = sum(player_reputations) / num_players
            average_diffs = map(lambda r : (average - r) ** 2, player_reputations)
            std_deviation = math.sqrt(sum(average_diffs) / num_players)

            if std_deviation <= 0.5:
                goal_rep = average
            else:
                distribution = [0, 0, 0, 0, 0, 0, 0, 0]
                i = 0

                while i < num_players:
                    distribution[self._distribution_index(player_reputations[i])] += 1
                    i += 1

                goal_rep = self._distribution_value(distribution.index(max(distribution)))

        goal_rep *= self.target_modifier
        return self._target_hunts(goal_rep, num_players)

    def _hunt_choices(self, round_number, current_food, current_reputation, m, player_reputations):
        if self.first_round_number is None:
            self.first_round_number = round_number

        if self.first_round_number == round_number:
            self.is_first_round = True
        else:
            self.is_first_round = False

        self.current_reputation = current_reputation
        num_players = len(player_reputations)
        self.next_total_moves = self.total_moves + num_players

        # phase 1 -> try to track known players
        if not self.is_first_round:
            i = 0

            while i < num_players:
                self.tracker.resolve(i, player_reputations[i])
                i += 1
        else:
            # it is the first round -> do nothing
            pass

        # phase 2 -> update tracker for next round
        i = 0

        while i < num_players:
            if not self.is_first_round:
                player_hunts = player_reputations[i] * self.total_moves
                new_pr_max = (player_hunts + num_players) / self.next_total_moves
                new_pr_min = player_hunts / self.next_total_moves
            else:
                # save some math
                new_pr_max = 1.0
                new_pr_min = 0.0

            self.tracker.track(i, player_reputations[i], new_pr_min, new_pr_max)
            i += 1

        # phase 3 -> make decisions
        target_hunts = self._determine_target_hunts(player_reputations)
        hunts_given = 0
        i = 0
        moves = []

        while i < num_players:
            if self.tracker.player_is_known(i) and \
                self.tracker.player_tracking_is_stable(i) and \
                hunts_given < target_hunts:
                if self.tracker.player_tends_to_hunt(i) and \
                    self._random_chance(self.tracker.player_rank(i)):
                    moves += ["h"]
                    hunts_given += 1
                else:
                    moves += ["s"]
            else:
                moves += [Player.filler]

            i += 1

        target_hunts -= hunts_given

        distribution_cluster = [0, 0, 0, 0, 0, 0, 0, 0]
        cluster_players = []
        distribution_remaining = [0, 0, 0, 0, 0, 0, 0, 0]
        remaining_players = []
        i = 0

        while i < num_players:
            if self.tracker.player_in_cluster(i):
                cr = self.tracker.cluster_reputation(i)
                distribution_cluster[self._distribution_index(cr)] += 1
                cluster_players += [(cr, i)]
            else:
                r = player_reputations[i]
                distribution_remaining[self._distribution_index(r)] += 1
                remaining_players += [(r, i)]

            i += 1

        cluster_players = sorted(cluster_players, reverse=True)
        remaining_players = sorted(remaining_players, reverse=True)
        assert len(distribution_cluster) == len(distribution_remaining)
        distribution_index = len(distribution_cluster) - 1 # start at the top tier
        cluster_index = 0
        remaining_index = 0
        hunts_given = 0

        while hunts_given < target_hunts:
            if distribution_index < 0:
                break

            while hunts_given < target_hunts and \
                cluster_index < int(distribution_cluster[distribution_index] * .75):
                if self._random_chance(self.tracker.cluster_rank(cluster_players[cluster_index][1])):
                    moves[cluster_players[cluster_index][1]] = "h"
                    hunts_given += 1
                else:
                    moves[cluster_players[cluster_index][1]] = "s"

                cluster_index += 1

            while hunts_given < target_hunts and \
                remaining_index < int(distribution_remaining[distribution_index] * .75):
                if self._random_chance(player_reputations[remaining_players[remaining_index][1]]):
                    moves[remaining_players[remaining_index][1]] = "h"
                    hunts_given += 1
                else:
                    moves[remaining_players[remaining_index][1]] = "s"

                remaining_index += 1

            if distribution_index - 1 >= 0:
                while hunts_given < target_hunts and \
                    cluster_index < int(distribution_cluster[distribution_index - 1] * .25):
                    if self._random_chance(self.tracker.cluster_rank(cluster_players[cluster_index][1])):
                        moves[cluster_players[cluster_index][1]] = "h"
                        hunts_given += 1
                    else:
                        moves[cluster_players[cluster_index][1]] = "s"

                    cluster_index += 1

                while hunts_given < target_hunts and \
                    remaining_index < int(distribution_remaining[distribution_index - 1] * .25):
                    if self._random_chance(player_reputations[remaining_players[remaining_index][1]]):
                        moves[remaining_players[remaining_index][1]] = "h"
                        hunts_given += 1
                    else:
                        moves[remaining_players[remaining_index][1]] = "s"

                    remaining_index += 1

            while hunts_given < target_hunts and \
                cluster_index < distribution_cluster[distribution_index]:
                if self._random_chance(self.tracker.cluster_rank(cluster_players[cluster_index][1])):
                    moves[cluster_players[cluster_index][1]] = "h"
                    hunts_given += 1
                else:
                    moves[cluster_players[cluster_index][1]] = "s"

                cluster_index += 1

            while hunts_given < target_hunts and \
                remaining_index < distribution_remaining[distribution_index]:
                if self._random_chance(player_reputations[remaining_players[remaining_index][1]]):
                    moves[remaining_players[remaining_index][1]] = "h"
                    hunts_given += 1
                else:
                    moves[remaining_players[remaining_index][1]] = "s"

                remaining_index += 1

            distribution_index -= 1

        while Player.filler in moves:
            moves[moves.index(Player.filler)] = "s"

        assert Player.filler not in moves
        self.total_moves = self.next_total_moves
        self.my_hunts += moves.count("h")
        return moves

    def _random_chance(self, p):
        assert p >= 0.0 and p <= 1.0, p
        # if p is 0, we want a low chance
        # if p is 1, we want a high chance
        r = random.random()
        return r <= (self._expansion(p) * self.chance_modifier)

    def _expansion(self, p):
        return (p / 2.0 ) + 0.5

    def _hunt_outcomes(self, food_earnings):
        i = 0
        num_players = len(food_earnings)
        successful_hunts = 0
        successful_slacks = 0
        total_hunts = 0
        total_slacks = 0

        while i < num_players:
            # remember how the player has acted towards us this round
            self.tracker.remember(i, self._player_move(food_earnings[i]))
            successful_hunts += self._successful_hunt(food_earnings[i])
            successful_slacks += self._successful_slack(food_earnings[i])

            if self._my_move(food_earnings[i]) == "h":
                total_hunts += 1
            else:
                total_slacks += 1

            i += 1

        if total_hunts > 0:
            successful_hunts_to_hunts = float(successful_hunts) / total_hunts
        else:
            successful_hunts_to_hunts = 0

        if total_slacks > 0:
            successful_slacks_to_slacks = float(successful_slacks) / total_slacks
        else:
            successful_slacks_to_slacks = 0

        self.target_modifier -= ((self.target_modifier - successful_hunts_to_hunts) / 2.0)   # divide by 2 to dampen change
        self.chance_modifier -= ((self.chance_modifier - successful_slacks_to_slacks) / 4.0) # divide by 4 to dampen change

    def _successful_hunt(self, earning):
        return 1 if earning == 0 else 0

    def _successful_slack(self, earning):
        return 1 if earning == 1 else 0

    def _my_move(self, earning):
        if earning == -3 or earning == 0:
            return "h"
        elif earning == -2 or earning == 1:
            return "s"

    def _player_move(self, earning):
        if earning == 1 or earning == 0:
            return "h"
        elif earning == -2 or earning == -3:
            return "s"


class PlayerState(object):
    def __init__(self, pid):
        super(PlayerState, self).__init__()
        self.pid = pid
        self.move = None
        self.previous_state = None

    def set_move(self, move):
        assert self.move is None
        self.move = move

    def set_previous_state(self, player_state):
        assert self.previous_state is None
        self.previous_state = player_state

    def history(self, trim=10):
        if self.previous_state is None or trim > 0:
            return [self.move]
        else:
            return [self.move] + self.previous_state.history(trim - 1)


class Tracker(object):
    # phases:
    #  1: tracking    -> look through the players' reputations for future tracking
    #  2: remembering -> look through the players' moves (just made towards us)
    #  0: resolving   -> look through the players' reputations to match with previous tracking
    tracking, remembering, resolving = range(0, 3)

    def __init__(self):
        super(Tracker, self).__init__()
        self.ruler = Ruler()
        self.clusterizer = Clusterizer()

        # products of analysis
        self.partitions = None
        self.clusters = None
        self.previous_clusters = None

        # keyed by next_pid
        self.tracked_players = {}
        self.tracked_clusters = {}
        self.next_tracked_players = {}

        # meta
        self.phase = Tracker.resolving # we always start by resolving

    def resolve(self, next_pid, current_reputation):
        if self.phase == Tracker.remembering:
            self.phase = Tracker.resolving
            self._analyze()
            self.next_tracked_players = {}
            self.tracked_clusters = {}
        elif self.phase == Tracker.tracking:
            raise RuntimeError("phase %d cannot go to resolve phase %d" % \
                               (self.phase, Tracker.resolving))

        previous_pid = self.partitions.find(current_reputation)

        # tracking a specific player takes priority over tracking in a group
        if previous_pid is not None:
            # this is a player we can match to the previous round! (woo!)
            player_state = PlayerState(next_pid)

            # check if we have a history
            if previous_pid in self.tracked_players:
                player_state.set_previous_state(self.tracked_players[previous_pid])
            # otherwise, this is the first time we've started tracking this player
            else:
                pass

            self.next_tracked_players[next_pid] = player_state

        previous_cluster = self.clusters.find(current_reputation, True)

        if previous_cluster is not None:
            # this is a player we can categorize in as a part
            # of a cluster from the previous round! (again, woo!)
            self.tracked_clusters[next_pid] = previous_cluster

    def track(self, previous_pid, previous_rep, next_min, next_max):
        if self.phase == Tracker.resolving:
            self.phase = Tracker.tracking
            self.tracked_players = self.next_tracked_players
            self.ruler = Ruler()
            self.clusterizer = Clusterizer()
        elif self.phase == Tracker.remembering:
            raise RuntimeError("phase %d cannot go to track phase %d" % \
                               (self.phase, Tracker.tracking))

        self.ruler.add(previous_pid, next_min, next_max)
        self.clusterizer.add(previous_pid, previous_rep, next_min, next_max)

    def remember(self, previous_pid, move):
        if self.phase == Tracker.tracking:
            self.phase = Tracker.remembering
        elif self.phase == Tracker.resolving:
            raise RuntimeError("phase %d cannot go to remember phase %d" % \
                               (self.phase, Tracker.remembering))

        self.clusterizer.remember(previous_pid, move)

        if previous_pid in self.tracked_players:
            self.tracked_players[previous_pid].set_move(move)

    def _analyze(self):
        self.partitions = self.ruler.analyze()
        self.previous_clusters = self.clusters
        self.clusters = self.clusterizer.analyze()

        if self.previous_clusters is not None:
            for cluster in self.clusters:
                similar_previous_cluster = self._find_similar_previous_cluster(cluster)

                if similar_previous_cluster is not None:
                    cluster.set_previous_cluster(similar_previous_cluster)

    def _find_similar_previous_cluster(self, cluster):
        similars = []

        for previous_cluster in self.previous_clusters:
            # the size is about the same
            if len(previous_cluster) * 1.1 >= len(cluster) and \
                len(previous_cluster) * .9 <= len(cluster):
                # the lower bound is about the same
                if previous_cluster.minimum + 0.05 >= cluster.minimum and \
                    previous_cluster.minimum - 0.05 <= cluster.minimum:
                    # the upper bound is about the same
                    if previous_cluster.maximum + 0.05 >= cluster.maximum and \
                        previous_cluster.maximum - 0.05 <= cluster.maximum:
                        similars += [previous_cluster]

        if len(similars) == 1:
            return similars[0]

    def player_is_known(self, next_pid):
        return next_pid in self.tracked_players

    def player_in_cluster(self, next_pid):
        return next_pid in self.tracked_clusters

    def player_tracking_is_stable(self, next_pid):
        return len(self.tracked_players[next_pid].history()) >= 3

    def player_rank(self, next_pid):
        history = self.tracked_players[next_pid].history()
        repeatability = len(history) * 2 / 10.0 # the *2 makes it weighted, because repeatability is more important
        reputation = float(history.count("h")) / len(history)
        return (reputation + repeatability) / 3.0

    def cluster_rank(self, next_pid):
        history = self.tracked_clusters[next_pid].history()
        repeatability = len(history) * 2 / 10.0 # the *2 makes it weighted, because repeatability is more important
        reputation = sum(history) / len(history)
        return (reputation + repeatability) / 3.0

    def player_tends_to_hunt(self, next_pid):
        history = self.tracked_players[next_pid].history()

        # if there are at least 3 recorded moves for the player
        if len(history) >= 3:
            # if the last 3 of 4 moves have been hunts
            recently_hunting = history[0:4].count("h") >= 3
            # if the average hunt rate is at least 2 of 3
            generally_hunting = (float(history.count("h")) / len(history)) >= 2.0 / 3.0
            return recently_hunting and generally_hunting

    def cluster_reputation(self, next_pid):
        history = self.tracked_clusters[next_pid].history()
        return sum(history) / len(history)


class Ranges(object):
    lower, upper, data = range(0, 3)

    def __init__(self):
        super(Ranges, self).__init__()
        self._ranges = []
        self.unfinished_range = None

    def start(self, lower_value, data):
        self.unfinished_range = {Ranges.lower: lower_value, Ranges.data: data}
        self._ranges += [self.unfinished_range]

    def finish(self, upper_value):
        assert upper_value > self.unfinished_range[Ranges.lower]
        self.unfinished_range[Ranges.upper] = upper_value
        self.unfinished_range = None

    def is_in_progress(self):
        return self.unfinished_range is not None

    def in_progress_data(self):
        return self.unfinished_range[Ranges.data]

    def __len__(self):
        return len(self._ranges)

    def __iter__(self):
        for r in self._ranges:
            yield r[Ranges.data]

    def __str__(self):
        out = "Ranges: [\n"

        for r in self._ranges:
            out += "lower: %f, upper: %f, data: %s,\n" % \
                (r[Ranges.lower], r[Ranges.upper], r[Ranges.data])

        return out + "]"

    def find(self, value, inclusive=False):
        # binary search for current_reputation in the ranges
        lower = 0
        upper = len(self._ranges) - 1
        i = int((upper - lower) / 2)
        searched = [i]

        if len(self._ranges) == 0:
            return None

        (lower_bound_check, upper_bound_check) = self._bounds_checks(i, value, inclusive)

        while lower_bound_check or upper_bound_check:
            if lower_bound_check:
                upper = i
            elif upper_bound_check:
                lower = i
            else:
                assert False

            delta = int(math.ceil(float(upper - lower) / 2))

            if lower == i:
                i += delta
            else:
                i -= delta

            if i in searched:
                return None

            searched += [i]
            (lower_bound_check, upper_bound_check) = self._bounds_checks(i, value, inclusive)

        return self._ranges[i][Ranges.data]

    def _bounds_checks(self, i, value, inclusive):
        lower_bound_check = None
        upper_bound_check = None

        if not inclusive:
            lower_bound_check = value <= self._ranges[i][Ranges.lower]
        else:
            lower_bound_check = value < self._ranges[i][Ranges.lower]

        if not inclusive:
            upper_bound_check = value >= self._ranges[i][Ranges.upper]
        else:
            upper_bound_check = value > self._ranges[i][Ranges.upper]

        return (lower_bound_check, upper_bound_check)


class Clusterizer(object):
    # i know, aweful name ;)
    def __init__(self):
        super(Clusterizer, self).__init__()
        self.points = {}
        self.used_pids = []
        self.ordered_points = []
        self.remembered_queries = {}

    def add(self, pid, value, left, right):
        self.points[pid] = Point(pid, value, left, right)
        self.ordered_points += [self.points[pid]]

    def remember(self, pid, move):
        self.points[pid].set_move(move)

    def analyze(self):
        #
        # based off DBSCAN cluster algorithm
        #

        # epsilon from DBSCAN (ie: the farthest a point can be from another to belong to the same cluster)
        max_difference = .05
        # clusters must contain at least 10% of the population
        min_cluster_size = int(math.ceil(len(self.points) * .1))
        # clusters must be at least 2 (otherwise thats not a cluster..)
        min_cluster_size = 2 if min_cluster_size < 2 else min_cluster_size
        # only allow up to %10 of the cluster's size to immigrate
        # (this is the small but negligable amount of players we allow to
        # fall within the new range of the cluster)
        max_immigration = .1
        clusters = Ranges()
        self.used_pids = []
        self.remembered_queries = {}
        self.ordered_points = sorted(self.ordered_points)

        for point in self.ordered_points:
            if not point.is_visited:
                point.visit()
                neighbours = self._region_query(point, max_difference)

                if len(neighbours) < min_cluster_size:
                    # point is 'noise'
                    pass
                else:
                    cluster = self._expand_cluster(point,
                                                   neighbours,
                                                   max_difference,
                                                   min_cluster_size)
                    # this extends the original DBSCAN to prune clusters which
                    # may have too many external players which may fall within
                    # the cluster's range
                    if self._immigration_compliant(cluster, max_immigration):
                        clusters.start(cluster.minimum, cluster)
                        clusters.finish(cluster.maximum)

        return clusters

    def _expand_cluster(self, point, neighbours, max_difference, min_cluster_size):
        cluster = Cluster(point)
        self.used_pids += [point.pid]
        index = 0

        while index < len(neighbours):
            if not neighbours[index].is_visited:
                neighbours[index].visit()
                other_neighbours = self._region_query(neighbours[index], max_difference)

                if len(other_neighbours) >= min_cluster_size:
                    for o in other_neighbours:
                        if o not in neighbours:
                            neighbours += [o]

            if neighbours[index].pid not in self.used_pids:
                self.used_pids += [neighbours[index].pid]
                cluster.add(neighbours[index])

            index += 1

        return cluster

    def _light_copy(self, point_list):
        # we need to deepcopy the list, but not deepcopy
        # the objects in the list
        return [p for p in point_list]

    def _immigration_compliant(self, cluster, max_immigration):
        max_immigrants = int(len(cluster) * max_immigration)
        immigrants = 0
        offset = 1
        bottom_index = self.ordered_points.index(cluster.bottom)
        top_index = self.ordered_points.index(cluster.top)
        continue_up = True
        continue_down = True

        while continue_up or continue_down:
            if top_index + offset < len(self.ordered_points):
                # strictly less than, because there may be multiple points
                # of the same value on the edge of the cluster
                if cluster.top.value < self.ordered_points[top_index + offset].value:
                    if self.ordered_points[top_index + offset].next_min <= cluster.maximum:
                        immigrants += 1
                    else:
                        continue_up = False
            else:
                continue_up = False

            if bottom_index - offset > -1:
                # strictly greater than, because there may be multiple points
                # of the same value on the edge of the cluster
                if cluster.bottom.value > self.ordered_points[bottom_index - offset].value:
                    if self.ordered_points[bottom_index - offset].next_max >= cluster.minimum:
                        immigrants += 1
                    else:
                        continue_down = False
            else:
                continue_down = False

            if immigrants > max_immigrants:
                break

            offset += 1

        return immigrants <= max_immigrants


    def _region_query(self, point, max_difference):
        assert point in self.ordered_points

        if point.pid in self.remembered_queries:
            return self._light_copy(self.remembered_queries[point.pid])

        region = [point]
        offset = 1
        index = self.ordered_points.index(point)
        continue_up = True
        continue_down = True

        while continue_up or continue_down:
            if index + offset < len(self.ordered_points):
                if point.value + max_difference >= self.ordered_points[index + offset].value:
                    region += [self.ordered_points[index + offset]]
                else:
                    continue_up = False
            else:
                continue_up = False

            if index - offset > -1:
                if point.value - max_difference <= self.ordered_points[index - offset].value:
                    region += [self.ordered_points[index - offset]]
                else:
                    continue_down = False
            else:
                continue_down = False

            offset += 1

        self.remembered_queries[point.pid] = region
        return self._light_copy(self.remembered_queries[point.pid])


class Cluster(object):
    def __init__(self, point):
        super(Cluster, self).__init__()
        self.bottom = point
        self.top = point
        self.minimum = point.next_min
        self.maximum = point.next_max
        self.size = 0
        self.hunts = 0
        self.add_move(point.move)
        self.previous_cluster = None

    def add_move(self, move):
        assert move == "h" or move == "s", "%s" % move
        self.size += 1

        if move == "h":
            self.hunts += 1

    def __len__(self):
        return self.size

    def add(self, point):
        if point.next_min < self.minimum:
            self.minimum = point.next_min

        if self.bottom.value > point.value:
            self.bottom = point

        if point.next_max > self.maximum:
            self.maximum = point.next_max

        if self.top.value < point.value:
            self.top = point

        self.add_move(point.move)

    def __repr__(self):
        return str(self)

    def __str__(self):
        return "(Cluster: %d, %d, %f, %f, %s, %s)" % \
            (self.size, self.hunts, self.minimum, self.maximum, self.bottom, self.top)

    def __eq__(self, other):
        return self.size == other.size and self.hunts == other.hunts

    def set_previous_cluster(self, previous_cluster):
        assert self.previous_cluster is None
        self.previous_cluster = previous_cluster

    def reputation(self):
        if self.size == 0:
            return 0.0

        return float(self.hunts) / self.size

    def history(self, trim=10):
        if self.previous_cluster is None or trim > 0:
            return [self.reputation()]
        else:
            return [self.reputation()] + self.previous_cluster.history(trim - 1)


class Point(object):
    def __init__(self, pid, value, next_min, next_max):
        super(Point, self).__init__()
        self.pid = pid
        self.value = value
        self.next_min = next_min
        self.next_max = next_max
        self.is_visited = False
        self.move = None

    def visit(self):
        self.is_visited = True

    def set_move(self, move):
        self.move = move

    def __eq__(self, other):
        return self.pid == other.pid

    def __cmp__(self, other):
        return cmp(self.value, other.value)

    def __repr__(self):
        return str(self)

    def __str__(self):
        return "(Point: %s, %f, %f, %f, %s)" % \
            (self.pid, self.value, self.next_min, self.next_max, self.move)


class Ruler(object):
    def __init__(self):
        super(Ruler, self).__init__()
        self._ruler = []
        self._sorted = True

    def analyze(self):
        ranges = Ranges()
        overlap_count = 0
        index = 0
        length = len(self)
        candidate_pid = None

        while index < len(self):
            pin = self[index]

            if pin.kind == Pin.left:
                overlap_count += 1
                # we only ever allow left pins to be candidates
                candidate_pid = pin.pid
            else:
                overlap_count -= 1

            ### process all the pins of this value at once
            # while there are pins in front of this pin, and
            # the next pin's value is equal to this one's
            while index + 1 < length and pin.value == self[index + 1].value:
                index += 1
                pin = self[index]

                if pin.kind == Pin.left:
                    overlap_count += 1
                    # we only ever allow left pins to be candidates
                    candidate_pid = pin.pid
                else:
                    overlap_count -= 1

            # if we already are working on a range
            if ranges.is_in_progress():
                # if the candidate has changed, or if the count of current ranges has changed
                if candidate_pid != ranges.in_progress_data() or overlap_count != 1:
                    ranges.finish(pin.value)

            if overlap_count == 1:
                ranges.start(pin.value, candidate_pid)

            index += 1

        return ranges

    def add(self, pid, left, right):
        assert left <= right
        self._sorted = False
        self._ruler += [Pin(left, pid, Pin.left)]
        self._ruler += [Pin(right, pid, Pin.right)]

    def __len__(self):
        return len(self._ruler)

    def __getitem__(self, index):
        if not self._sorted:
            self._sorted = True
            self._ruler = sorted(self._ruler)

        return self._ruler[index]

    def __iter__(self):
        if not self._sorted:
            self._sorted = True
            self._ruler = sorted(self._ruler)

        for p in self._ruler:
            yield p


class Pin(object):
    left, right = range(0, 2)

    def __init__(self, value, pid, kind):
        super(Pin, self).__init__()
        self.value = value
        self.pid = pid
        self.kind = kind

    def __str__(self):
        return "Pin: value: %s, pid: %s, kind: %s" % (self.value, self.pid, self.kind)

    def __cmp__(self, other):
        return cmp(self.value, other.value)

